package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode120 {

    //solution 1:
//    public int minimumTotal(List<List<Integer>> triangle) {
//        int n = triangle.size();
//        Integer[][]mini = new Integer[n][n];
//        //最后一行，节点的值就是路径的值
//        mini[n-1] = (Integer[])(triangle.get(triangle.size()-1).toArray());
//
//        //从倒数第二行开始
//        for (int i = triangle.size() - 2; i >= 0; i--) {
//            for (int j = 0; j < triangle.get(i).size(); j++) {
//                //当前节点和它的两个子节点，只保留最小的路径
//                //j+1不会越界，因为跳过了最后一行
//                mini[i][j] = triangle.get(i).get(j) + Math.min(mini[i+1][j], mini[i+1][j+1]);
//            }
//        }
//
//        return mini[0][0];
//    }


    /*
    //solution 2:  （solution 1优化）根据动态规划
    //我们要逆向的推算，从倒数第二行开始算起，DP[i][j] = Math.min(DP[i+1][j],DP[i+1][j+1]) + triangle[i][j]
    //就是说，当前节点的最小路径值 = 它的子节点的最小路径值 + 当前节点的值
    // 时间复杂度：O(n*n),空间复杂度：O(n)
    public int minimumTotal(List<List<Integer>> triangle) {
        //取出最后一行数据,最后一行数据没有子节点，它本身的值就是路径的值
        Integer[]mini = (Integer[])(triangle.get(triangle.size()-1).toArray());
        //从倒数第二行开始
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                //当前节点和它的两个子节点，只保留最小的路径
                //mini：将新的一行的最小路径值保留在mini，达到重复利用的效果
                //j+1不会越界，因为跳过了最后一行;回到第一行的时候，只有一个数
                mini[j] = triangle.get(i).get(j) + Math.min(mini[j], mini[j+1]);
            }
        }

        //倒着数，回到第一行的时候，只有一个数
        return mini[0];
    }
*/

    private int sum = 0;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null && triangle.size() == 0) {
            return 0;
        }


        return _dfs(triangle, 0, 0);
    }

    private int _dfs(List<List<Integer>> triangle, int i, int j) {
        //结束条件
        if (i >= triangle.size()-1) {
           return 1;
        }
        //处理

        //递归
        //清除状态
        return 0;
    }

    public String addString(String str){
        str = "b";

        return str;
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> triangle1 = Arrays.asList(2);
        List<Integer> triangle2 = Arrays.asList(3, 4);
        List<Integer> triangle3 = Arrays.asList(6, 5, 7);
        List<Integer> triangle4 = Arrays.asList(4, 1, 8, 3);
        triangle.add(triangle1);
        triangle.add(triangle2);
        triangle.add(triangle3);
        triangle.add(triangle4);

        Leetcode120 leetcode = new Leetcode120();
//        System.out.println(leetcode.minimumTotal(triangle));

        String original = "a";
        System.out.println(leetcode.addString(original));
        System.out.println(original);
    }
}
